# LeetCode 463、岛屿的周长
# 一、题目描述
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。 示例 1：
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边
示例 2：
输入：grid = [[1]]
输出：4
示例 3：
输入：grid = [[1,0]]
输出：4
提示：
row == grid.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j]为0或1
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode.cn/problems/island-perimeter/
class Solution {
public int islandPerimeter(int[][] grid) {
// 矩阵的行数
int m = grid.length;
// 矩阵的列数
int n = grid[0].length;
// 从左到右，一行行开始搜索
for (int i = 0; i < m; i++) {
// 从上到下，一列列开始搜索
for (int j = 0; j < n; j++) {
// 如果当前格子是陆地，才有资格继续延伸搜索下去
if(grid[i][j] == 1){
// 题目说明，恰好有一个岛屿
return dfs(grid,i,j);
}
}
}
return 0;
}
public int dfs(int[][] grid, int i, int j) {
// dfs搜索、递归终止条件
// i < 0 ，越界
// j < 0 ，越界
// i >= board.length ，越界
// j >= board[0].length ，越界
// 从边界格子向外面延伸，会提供一条边的周长
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length ) {
return 1;
}
// 如果当前格子是水域，会提供一条边的周长
if(grid[i][j] == 0){
return 1;
}
// 如果当前格子已经遍历过的陆地，无法提供边
if(grid[i][j] == 2){
return 0;
}
// 否则说明当前位置实际上是陆地，为 1
// 需要把它修改为 2，代表是已经访问过陆地
grid[i][j] = 2;
// 在当前单元格的四个方向开始搜索
// 上：（ 0 ， -1 ）
// 下：（ 0 ， 1 ）
// 左：（ -1 ， 0 ）
// 右：（ 1 ， 0 ）
// dx 为行的方向数组
int dx[] = { -1 , 1 , 0 , 0 };
// dy 为行的方向数组
int dy[] = { 0 , 0 , -1 , 1 };
// 以当前这个陆地格子 grid[i][j] 的四周搜索下去，计算周长
int res = 0;
// 朝着这四个方向开始延伸搜索下去
for (int index = 0; index < 4; ++index) {
// 下一个即将去搜索网格的横坐标
int next_i = i + dx[index];
// 下一个即将去搜索网格的纵坐标
int next_j = j + dy[index];
// 获取从（ next_i ，next_j ）这个网格开始出发延伸之后的周长
int circle = dfs(grid, next_i,next_j);
// 把这个新增的周长累加到（ i ， j ）这个网格上
res += circle;
}
// 返回从 grid[i][j] 这个格子开始延伸得到的周长
return res;
}
}
# **2、**C++ 代码
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
// 矩阵的行数
int m = grid.size();
// 矩阵的列数
int n = grid[0].size();
// 从左到右，一行行开始搜索
for (int i = 0; i < m; i++) {
// 从上到下，一列列开始搜索
for (int j = 0; j < n; j++) {
// 如果当前格子是陆地，才有资格继续延伸搜索下去
if(grid[i][j] == 1){
// 题目说明，恰好有一个岛屿
return dfs(grid,i,j);
}
}
}
return 0;
}
public:
int dfs(vector<vector<int>>& grid, int i, int j) {
// dfs搜索、递归终止条件
// i < 0 ，越界
// j < 0 ，越界
// i >= board.length ，越界
// j >= board[0].length ，越界
// board[i][j] == X ，不需要继续搜索下去
// board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() ) {
return 1 ;
}
// 如果当前格子是水域，会提供一条边的周长
if(grid[i][j] == 0){
return 1;
}
// 如果当前格子已经遍历过的陆地，无法提供边
if(grid[i][j] == 2){
return 0;
}
// 否则说明当前位置实际上是陆地，为 1
// 需要把它修改为 2，代表是已经访问过陆地
grid[i][j] = 2;
// 在当前单元格的四个方向开始搜索
// 上：（ 0 ， -1 ）
// 下：（ 0 ， 1 ）
// 左：（ -1 ， 0 ）
// 右：（ 1 ， 0 ）
// dx 为行的方向数组
int dx[4] = { -1 , 1 , 0 , 0 };
// dy 为行的方向数组
int dy[4] = { 0 , 0 , -1 , 1 };
// 以当前这个陆地格子 grid[i][j] 的四周搜索下去，计算周长
int res = 0;
// 朝着这四个方向开始延伸搜索下去
for (int index = 0; index < 4; index++) {
// 下一个即将去搜索网格的横坐标
int next_i = i + dx[index];
// 下一个即将去搜索网格的纵坐标
int next_j = j + dy[index];
// 获取从（ next_i ，next_j ）这个网格开始出发延伸之后的周长
int circle = dfs(grid, next_i,next_j);
// 把这个新增的周长累加到（ i ， j ）这个网格上
res += circle;
}
return res;
}
};
# 3、Python 代码
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
# 矩阵的行数
m = len(grid)
# 矩阵的列数
n = len(grid[0])
# 利用两个 for 循环，遍历矩阵中的一些特殊的单元格，将它们赋值为 N
# 特殊的单元格：必然是从边界处开始的
for i in range(0 , m ) :
for j in range( 0 , n ):
if(grid[i][j] == 1):
return self.dfs(grid, i, j)
return 0
def dfs(self, grid: List[List[str]], i : int , j : int ) -> int:
# dfs搜索、递归终止条件
# i < 0 ，越界
# j < 0 ，越界
# i >= board.length ，越界
# j >= board[0].length ，越界
# board[i][j] == X ，不需要继续搜索下去
# board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) :
return 1
if grid[i][j] == 0 : return 1
if grid[i][j] == 2 : return 0
# 否则说明当前位置实际上是陆地，为 1
# 需要把它修改为 2，代表是已经访问过陆地
grid[i][j] = 2
res = 0
# 在当前单元格的四个方向开始搜索
# 上：（ 0 ， -1 ）
# 下：（ 0 ， 1 ）
# 左：（ -1 ， 0 ）
# 右：（ 1 ， 0 ）
# 朝着这四个方向开始延伸搜索下去
for dx, dy in ((0,1), (1,0), (0,-1), (-1,0)):
# 下一个即将去搜索网格的横坐标
next_i = i + dx
# 下一个即将去搜索网格的纵坐标
next_j = j + dy
circle = self.dfs(grid,next_i,next_j)
res += circle
return res
# 四、复杂度分析
时间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。深度优先搜索过程中，每一个点至多只会被标记一次。
空间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。